#include<iostream>
#include<stdlib.h>
using namespace std;
int gcd(int a,int b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}
void factor(int n)
{
    int x=rand(),y,k=2,i=1;
    while (true)
    {
        /* code */
        i++;
        x=(x*x-1)%n;
        int d=gcd((((y-x)%n)+n)%n,n);
        if(d>1&&d<n) cout<<d<<" "<<i,exit(0);
        if(i==k)
        {
            k*=2;
            y=x;
        }
    }
    
}
int main()
{
    factor(1387);
}